package org.lql.algo.codecrush.hot100.binaryTree;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-09-07 16:27
 * @description: 105. 从前序与中序遍历序列构造二叉树 <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class BuildTree {

	int[] preorder;
	int[] inorder;

	/**
	 * 前序遍历：根-左-右
	 * <p>
	 * 中序遍历：左-根-右
	 * <p>
	 * 后序遍历：左-右-根
	 */
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		this.preorder = preorder; // 根-左-右
		this.inorder = inorder; // 左-根-右
		return build(0, preorder.length - 1, 0, inorder.length - 1);
	}

	private TreeNode build(int preStart, int preEnd, int inStart, int inEnd) {
		if (preStart > preEnd) {
			return null;
		}
		// 前序遍历初始跟节点
		int rootVal = preorder[preStart];
		TreeNode root = new TreeNode(rootVal);
		// 寻找中序遍历的根节点位置
		int rootIndex = 0;
		while (rootIndex < inEnd && inorder[rootIndex] != rootVal) {
			rootIndex++;
		}
		// 在中序遍历中确定左、右子树
		int leftSize = rootIndex - inStart;
		root.left = build(preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
		root.right = build(preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
		return root;
	}
}
